package com.xinwei.leetcode.数组;

// https://leetcode-cn.com/problems/jump-game/

// 最基本的跳到0就意味着false
// 递归写法  -->时间超出限制
public class _55_跳跃游戏 {
    boolean res = false;
    public boolean canJump(int[] nums) {
        if (nums.length == 1 && nums[0] == 0) return res;
        jump(0, nums);
        return res;
    }

    public void jump(int index, int[] nums) {
        if (index >= nums.length) {
            res = true;
            return;
        }
        if (nums[index] == 0 && index != nums.length - 1) return;
        if (nums[index] != 0){
            for (int i = 1; i <= nums[index]; i++) {
                jump(index + i, nums);
            }
        }else {
            res = true;
            return;
        }
    }

    // 从后往前找，找可以跳的点
    public boolean canJump1(int[] nums) {
        int canJump = nums.length - 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (canJump - i <= nums[i]) {
                canJump = i;
            }else {
                continue;
            }
        }
        if (canJump == 0) return true;
        return false;
    }
}
